/*
 * This source file is part of ARK
 * For the latest info, see https://github.com/ArkNX
 *
 * Copyright (c) 2013-2019 ArkNX authors.
 *
 * Licensed under the Apache License, Version 2.0 (the "License"),
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 */

#pragma once

#include "base/AFCoreDef.hpp"
#include "base/AFMacros.hpp"

namespace ark {

template<typename TYPE>
class AFStringTraits
{
};

template<>
class AFStringTraits<char>
{
public:
    static size_t Hash(const char* value)
    {
        return GetHashValue(value);
    }

    static size_t Length(const char* value)
    {
        return strlen(value);
    }

    static bool Equal(const char* lvalue, const char* rvalue)
    {
        return (0 == strcmp(lvalue, rvalue));
    }

    static void Copy(char* dst, const char* src, size_t len)
    {
        memcpy(dst, src, len);
    }
};

template<typename TYPE>
class AFStringTraitsNoCase : public AFStringTraits<TYPE>
{
};

template<>
class AFStringTraitsNoCase<char> : public AFStringTraits<char>
{
public:
    static size_t hash(const char* value)
    {
        return GetHashValueNoCase(value);
    }

    static bool equal(const char* lvalue, const char* rvalue)
    {
        return (0 == ARK_STRICMP(lvalue, rvalue));
    }
};
//////////////////////////////////////////////////////////////////////////
class AFStringPodAlloc
{
public:
    AFStringPodAlloc() = default;
    ~AFStringPodAlloc() = default;

    void* Alloc(size_t size)
    {
        ARK_NEW_ARRAY_RET(char, size);
    }

    void Free(void* ptr, size_t size)
    {
        ARK_DELETE_ARRAY(char, ptr);
    }

    void Swap(AFStringPodAlloc& src)
    {
        // Do nothing
    }
};

template<typename TYPE, typename DATA>
class AFStringPodNode
{
public:
    AFStringPodNode* next;
    size_t hash;
    DATA data;
    TYPE name[1]; // like TYPE* name /  char* name
};

//////////////////////////////////////////////////////////////////////////

// predeclared
template<typename TYPE, typename DATA, typename TRAITS = AFStringTraits<TYPE>, typename ALLOC = AFStringPodAlloc>
class AFStringPod;

template<typename TYPE, typename DATA, typename TRAITS = AFStringTraits<TYPE>, typename ALLOC = AFStringPodAlloc>
class AFStringPodIter
{
private:
    using hash_t = AFStringPod<TYPE, DATA, TRAITS, ALLOC>;
    using node_t = AFStringPodNode<TYPE, DATA>;

public:
    AFStringPodIter() = delete;

    AFStringPodIter(const hash_t* self, node_t* node)
        : mpSelf(self)
        , mpNode(node)
    {
    }

    AFStringPodIter& operator++()
    {
        node_t* next = mpNode->next;

        if (next != nullptr)
        {
            mpNode = next;
        }
        else
        {
            mpNode = mpSelf->ToNext(mpNode);
        }

        return *this;
    }

    AFStringPodIter& operator++(int)
    {
        AFStringPodIter tmp(*this);
        ++(*this);
        return tmp;
    }

    bool operator==(const AFStringPodIter& other) const
    {
        return (mpNode == other.mpNode);
    }

    bool operator!=(const AFStringPodIter& other) const
    {
        return (mpNode != other.mpNode);
    }

    const TYPE* GetKey() const
    {
        return mpNode->name;
    }

    DATA* GetData() const
    {
        return mpNode->data;
    }

    node_t* GetNode() const
    {
        return mpNode;
    }

private:
    const hash_t* mpSelf;
    node_t* mpNode;
};

template<typename TYPE, typename DATA, typename TRAITS, typename ALLOC>
class AFStringPod
{
private:
    using hash_t = AFStringPod<TYPE, DATA, TRAITS, ALLOC>;
    using node_t = AFStringPodNode<TYPE, DATA>;

    using iterator = AFStringPodIter<TYPE, DATA, TRAITS, ALLOC>;
    using const_iterator = AFStringPodIter<TYPE, DATA, TRAITS, ALLOC>;

public:
    explicit AFStringPod(size_t size = 0)
        : mnSize(size)
    {
        mnCount = 0;

        if (size > 0)
        {
            mpBuckets = (node_t**)mxAlloc.Alloc(sizeof(node_t*) * size);
            memset(mpBuckets, 0, sizeof(node_t*) * size);
        }
        else
        {
            mpBuckets = NULL;
        }
    }

    AFStringPod(const hash_t& src)
    {
        const size_t size = src.mnSize;
        mnCount = 0;
        mnSize = size;

        if (size > 0)
        {
            mpBuckets = (node_t**)mxAlloc.Alloc(sizeof(node_t*) * size);
            memset(mpBuckets, 0, sizeof(node_t*) * size);

            for (size_t i = 0; i < size; ++i)
            {
                node_t* p = src.mpBuckets[i];

                while (p)
                {
                    if (!Add(p->name, p->data))
                    {
                        ARK_ASSERT(0, "Add fail ", __FILE__, __FUNCTION__);
                    }

                    p = p->next;
                }
            }
        }
        else
        {
            mpBuckets = NULL;
        }
    }

    ~AFStringPod()
    {
        Clear();

        if (mpBuckets)
        {
            mxAlloc.Free(mpBuckets, sizeof(node_t*) * mnSize);
        }
    }

    void Swap(hash_t& src)
    {
        node_t** tmp_buckets = src.mpBuckets;
        size_t tmp_size = src.mnSize;
        size_t tmp_count = src.mnCount;

        src.mpBuckets = this->mpBuckets;
        src.mnSize = this->mnSize;
        src.mnCount = this->mnCount;
        this->mpBuckets = tmp_buckets;
        this->mnSize = tmp_size;
        this->mnCount = tmp_count;
        mxAlloc.Swap(src.mxAlloc);
    }

    void Clear()
    {
        for (size_t i = 0; i < mnSize; ++i)
        {
            node_t* p = mpBuckets[i];

            while (p)
            {
                node_t* next = p->next;
                DeleteNode(p);
                p = next;
            }

            mpBuckets[i] = NULL;
        }
    }

    size_t GetCount() const
    {
        return mnCount;
    }

    bool Set(const TYPE* name, const DATA& data)
    {
        node_t* node = FindNode(name);

        if (node == nullptr)
        {
            return Add(name, data);
        }

        node->data = data;
        return true;
    }

    bool Add(const TYPE* name, const DATA& data)
    {
        assert(name != nullptr);

        if (mnCount == mnSize)
        {
            Expand();
        }

        size_t hash = TRAITS::Hash(name);
        size_t bucket = GetBucket(hash);
        node_t* p = NewNode(name);

        p->next = mpBuckets[bucket];
        p->hash = hash;
        p->data = data;

        mpBuckets[bucket] = p;
        ++mnCount;
        return true;
    }

    bool Add(const TYPE* name, const DATA& data, TYPE*& pName)
    {
        assert(name != nullptr);

        if (mnCount == mnSize)
        {
            Expand();
        }

        size_t hash = TRAITS::Hash(name);
        size_t bucket = GetBucket(hash);
        node_t* p = NewNode(name);

        p->next = mpBuckets[bucket];
        p->hash = hash;
        p->data = data;

        mpBuckets[bucket] = p;
        ++mnCount;

        pName = p->name;
        return true;
    }

    bool Remove(const TYPE* name)
    {
        assert(name != nullptr);

        if (mnSize == 0)
        {
            return false;
        }

        size_t hash = TRAITS::Hash(name);
        size_t bucket = GetBucket(hash);
        node_t* p = mpBuckets[bucket];

        while (p)
        {
            if ((p->hash == hash) && TRAITS::Equal(p->name, name))
            {
                EraseNode(bucket, p);
                DeleteNode(p);
                --mnCount;
                return true;
            }

            p = p->next;
        }

        return false;
    }

    bool RemoveData(const TYPE* name, const DATA& data)
    {
        assert(name != nullptr);

        if (mnSize == 0)
        {
            return false;
        }

        size_t hash = TRAITS::Hash(name);
        size_t bucket = GetBucket(hash);
        node_t* p = mpBuckets[bucket];

        while (p)
        {
            if ((p->hash == hash) && TRAITS::Equal(p->name, name) && (p->data == data))
            {
                EraseNode(bucket, p);
                DeleteNode(p);
                --mnCount;
                return true;
            }

            p = p->next;
        }

        return false;
    }

    bool exists(const TYPE* name) const
    {
        return (FindNode(name) != nullptr);
    }

    iterator find(const TYPE* name)
    {
        return iterator(this, FindNode(name));
    }

    const_iterator find(const TYPE* name) const
    {
        return const_iterator(this, FindNode(name));
    }

    bool GetData(const TYPE* name, DATA& data) const
    {
        node_t* p = FindNode(name);

        if (p == nullptr)
        {
            return false;
        }

        data = p->data;
        return true;
    }

    iterator Begin()
    {
        for (size_t i = 0; i < mnSize; ++i)
        {
            if (mpBuckets[i])
            {
                return iterator(this, mpBuckets[i]);
            }
        }

        return End();
    }

    iterator End()
    {
        return iterator(this, NULL);
    }

    const_iterator Begin() const
    {
        for (size_t i = 0; i < mnSize; ++i)
        {
            if (mpBuckets[i])
            {
                return const_iterator(this, mpBuckets[i]);
            }
        }

        return End();
    }

    const_iterator End() const
    {
        return const_iterator(this, NULL);
    }

    iterator Erase(iterator iter)
    {
        iterator tmp(iter);
        ++tmp;
        node_t* p = iter.GetNode();
        EraseNode(GetBucket(p->hash), p);
        DeleteNode(p);
        --mnCount;

        return tmp;
    }

    size_t get_mem_usage() const
    {
        size_t size = sizeof(hash_t);

        for (size_t i = 0; i < mnSize; ++i)
        {
            node_t* p = mpBuckets[i];

            while (p)
            {
                size += sizeof(node_t) + TRAITS::length(p->name) * sizeof(TYPE);
                p = p->next;
            }
        }

        size += sizeof(node_t) * mnSize;
        return size;
    }

protected:
    size_t GetBucket(size_t hash) const
    {
        return (hash % mnSize);
    }

    node_t* NewNode(const TYPE* name)
    {
        const size_t length = TRAITS::Length(name);
        const size_t size = sizeof(node_t) + length * sizeof(TYPE);
        node_t* p = (node_t*)mxAlloc.Alloc(size);
        TRAITS::Copy(p->name, name, length + 1);
        return p;
    }

    void DeleteNode(node_t* p)
    {
        mxAlloc.Free(p, sizeof(node_t) + TRAITS::Length(p->name) * sizeof(TYPE));
    }

    void EraseNode(size_t bucket, node_t* p)
    {
        assert(bucket < mnSize);
        assert(p != nullptr);

        node_t* node = mpBuckets[bucket];

        if (node == p)
        {
            mpBuckets[bucket] = p->next;
            return;
        }

        while (node)
        {
            if (node->next == p)
            {
                node->next = p->next;
                return;
            }

            node = node->next;
        }
    }

    node_t* FindNode(const TYPE* name) const
    {
        assert(name != nullptr);

        if (0 == mnSize)
        {
            return nullptr;
        }

        size_t hash = TRAITS::Hash(name);
        size_t bucket = GetBucket(hash);
        node_t* node = mpBuckets[bucket];

        while (node)
        {
            if ((node->hash == hash) && TRAITS::Equal(node->name, name))
            {
                return node;
            }

            node = node->next;
        }

        return nullptr;
    }

    void Expand()
    {
        size_t new_size = mnSize * 2 + 1; // hash bucket
        node_t** new_buckets = (node_t**)mxAlloc.Alloc(sizeof(node_t*) * new_size);
        memset(new_buckets, 0, sizeof(node_t*) * new_size);

        for (size_t i = 0; i < mnSize; ++i)
        {
            if (nullptr != mpBuckets)
            {
                node_t* p = mpBuckets[i];

                while (p)
                {
                    node_t* next = p->next;
                    size_t bucket = size_t(p->hash) % new_size;

                    p->next = new_buckets[bucket];
                    new_buckets[bucket] = p;
                    p = next;
                }
            }
        }

        if (mpBuckets)
        {
            mxAlloc.Free(mpBuckets, sizeof(node_t*) * mnSize);
        }

        mpBuckets = new_buckets;
        mnSize = new_size;
    }

    node_t* ToNext(node_t* node) const
    {
        assert(node != nullptr);

        for (size_t i = GetBucket(node->hash) + 1; i < mnSize; ++i)
        {
            if (mpBuckets[i])
            {
                return mpBuckets[i];
            }
        }

        return nullptr;
    }

private:
    friend class AFStringPodIter<TYPE, DATA, TRAITS, ALLOC>;
    ALLOC mxAlloc;
    node_t** mpBuckets;
    size_t mnSize;
    size_t mnCount;
};

} // namespace ark
